package algorithm.recursionAndbacktrack.twoDimensions.floodfill.p130;

/**
 * 130. 被围绕的区域
 */
class Solution {
    private int m;
    private int n;

    public void solve(char[][] board) {
        m = board.length;
        n = board[0].length;
        boolean[][] visited = new boolean[m][n];
        int[][] d = {{0, -1}, {1, 0}, {0, 1}, {-1, 0}};
        // 1.先从边界上的o出发，将与边界上的o相连的区域都排除掉
        // 纵向
        for (int i = 0; i < m; i++) {
            if(!visited[i][0] && board[i][0] == 'O') {
                dfs1(board, visited, d, i, 0);
            }
            if (!visited[i][n - 1] && board[i][n - 1] == 'O') {
                dfs1(board, visited, d, i, n - 1);
            }
        }
        // 横向
        for (int j = 0; j < n; j++) {
            if(!visited[0][j] && board[0][j] == 'O') {
                dfs1(board, visited, d, 0, j);
            }
            if (!visited[m - 1][j] && board[m - 1][j] == 'O') {
                dfs1(board, visited, d, m - 1, j);
            }
        }
        // 处理内部区域
        for (int i = 1; i < m - 1; i++) {
            for (int j = 1; j < n - 1; j++) {
                // 从所有没有被遍历过的O区域出发，将所有的O区域进行标注
                if (!visited[i][j] && board[i][j] == 'O') {
                    dfs2(board, visited, d, i, j);
                }
            }
        }
    }

    // 处理边界
    private void dfs1(char[][] board, boolean[][] visited, int[][] d, int x, int y) {
        visited[x][y] = true;
        for (int i = 0; i < d.length; i++) {
            int newX = x + d[i][0];
            int newY = y + d[i][1];
            if (inArea(newX, newY) && !visited[newX][newY] && board[newX][newY] == 'O') {
                dfs1(board, visited, d, newX, newY);
            }
        }
    }

    private void dfs2(char[][] board, boolean[][] visited, int[][] d, int x, int y) {
        visited[x][y] = true;
        board[x][y] = 'X';
        for (int i = 0; i < d.length; i++) {
            int newX = x + d[i][0];
            int newY = y + d[i][1];
            if (inArea(newX, newY) && !visited[newX][newY] && board[newX][newY] == 'O') {
                dfs2(board, visited, d, newX, newY);
            }
        }
    }

    private boolean inArea(int x, int y) {
        return x >= 0 && x < m && y >= 0 && y < n;
    }

    public static void main(String[] args) {
        /*char[][] board = {{'X', 'X', 'X', 'X', 'X'},
                          {'X', 'O', 'O', 'O', 'X'},
                          {'X', 'X', 'X', 'O', 'X'},
                          {'X', 'X', 'O', 'X', 'X'},
                          {'X', 'O', 'O', 'X', 'X'}};*/
        /*char[][] board = {{'X','X','X','X'},
                          {'X','O','O','X'},
                          {'X','X','O','X'},
                          {'X','O','X','X'}};*/
        char[][] board = {{'X','O','X','O','X','O'},
                          {'O','X','O','X','O','X'},
                          {'X','O','X','O','X','O'},
                          {'O','X','O','X','O','X'}};
        new Solution().solve(board);
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[0].length; j++) {
                System.out.print(board[i][j]);
            }
            System.out.println();
        }
    }
}